1. Field of the Invention
The present invention relates to a scheduler, and more particularly to a scheduler for a switching apparatus in an ATM network.
2. Description of the Related Art
Generally, when data on N (N is a positive integer equal to or more than 2) input paths should be fairly allocated to M (M is a positive integer equal to or more than 2) output paths, a scheduler uses shuffle patterns.
FIG. 1 shows the overview of the structure of the scheduler proposed in a conventional example. A similar technique is disclosed in Japanese Laid Open Patent Application (JP-A-Heisei 9-326828). The scheduler 100 is used in a crossbar switch of a packet switching apparatus, and has N input interfaces and M output interfaces (both not shown). The scheduler 100 allocates request data 101 to 10N for allocation request outputted from the first to N-th input interfaces M by M to the first to M-th output interfaces.
The scheduler 100 is composed of first to N-th output rearranging units 111 to 11N, input rearranging unit 129, a searching unit 139, and a shuffle pattern storage unit 151. The first to N-th output rearranging units 111 to 11N input N sets of M request data 101 to 10N outputted from the input interface units, respectively. The input rearranging unit 129 inputs N sets of M rearranged request data 121 to 12N from the first to N-th output rearranging units 111 to 11N. The N sets of M rearranged request data 131 to 13N outputted from the input rearranging unit 129 are supplied to the searching unit 139. The searching unit 139 outputs N permission signals 141 to 14N. The shuffle pattern storage unit 151 is provided for the scheduler 100 to store shuffle patterns for rearrangement of the request data. One 152 of the shuffle patterns is outputted from the shuffle pattern storage unit 151 to the first to N-th output rearranging units 111 to 11N, and is used for the rearrangement of the N sets of M request data 101 to 10N. Also, the other shuffle pattern 153 is outputted from the shuffle pattern storage unit 151 to the input rearranging unit 129, and is used for the rearrangement of the rearranged request data.
FIG. 2 shows a specific structure of the first output rearranging unit 111 in the conventional scheduler. The first to N-th output rearranging units 111 to 11N have the same structure. Therefore, the structure of the first output rearranging unit 111 will be described. The first output rearranging unit 111 is composed of a single rearranging unit 161 which inputs M request data 1011 to 101M. The Shuffle pattern 152 is supplied to the rearranging unit 161 from the shuffle pattern storage unit 151 shown in FIG. 1. The rearrangement of the M request data 1011 to 101M is carried out once in accordance with the shuffle pattern 152. The M rearranged request data 1211 to 121M are supplied to the input rearranging unit 129 shown in FIG. 1.
FIG. 3 shows a specific structure of the input rearranging unit of the scheduler 100 shown in FIG. 1. The input rearranging unit 129 is composed of a rearranging unit 176, which inputs N sets of M rearranged request data 121 to 12N. The shuffle pattern 153 is supplied from the shuffle pattern storage unit 151 shown in FIG. 1 to the rearranging unit 176. The rearrangement of the rearranged request data 121 to 12N is carried out once in accordance with the shuffle pattern 153. The rearranged request data 131 to 13N are supplied to the searching unit 139 shown in FIG. 1.
By the way, the rearrangement of the request data is carried out once in the rearranging units 161 and 176 shown in FIGS. 2 and FIG. 3, respectively. In such a conventional example, when the number of input paths is M which is different from the number of output paths N, the shuffle patterns need to be prepared individually. This will be described below.
FIG. 4 shows an example of the shuffle pattern used to rearrange twelve data. Only a part of such a shuffle pattern cannot be used for eight data which are less than twelve data. This will be further described. In the shuffle pattern for the twelve data shown in FIG. 4, values from xe2x80x9c1xe2x80x9d to xe2x80x9c12xe2x80x9d are randomly arranged in order of the access. At this time, it is supposed that eight shuffle data are fixedly taken out from the shuffle pattern shown in FIG. 4. In this case, it is necessary to contain all the values from xe2x80x9c1xe2x80x9d to xe2x80x9c8xe2x80x9d in eight shuffle data. However, it is impossible for the taken data to contain all the values from xe2x80x9c1xe2x80x9d to xe2x80x9c8xe2x80x9d. Therefore, the shuffle patterns need to be independently prepared depending on the size of data.
Now, the case that the value M is xe2x80x9c8xe2x80x9d and the value N is xe2x80x9c12xe2x80x9d will be described as an example. When the scheduling operation of 8xc3x9712 is carried out, the number of shuffle patterns used to rearrange eight data is xe2x80x9c40,320xe2x80x9d as factorial of eight for all the patterns of arrangement, because the amount of information is 24 bits. Also, in case of twelve data, one set of shuffle patterns is 48 bits, and the number of shuffle patterns is xe2x80x9c479,001,600xe2x80x9d as factorial of twelve. Therefore, the memory with the memory capacity of 40,320 wordsxc3x9724 bits and the memory with the memory capacity of 479,001,600 wordxc3x9748 bits need be prepared. Also, when access to the memories is carried out using a bus of eight bits, the memory access is carried out three times to read the shuffle pattern for eight data and six times to read the shuffle pattern for twelve data.
It could be considered that these two memories are accessed in parallel to reduce the access time. However, when such parallel access is carried out, it is necessary to prepare two sets of interface signals such as address signals and data control signal to access these two memories. Therefore, when the scheduler is realized as an integrated circuit such as LSI and FPGA, there would be a case that the number of terminals lacks.
In conjunction with the above description, the above Japanese Laid Open Patent Application (JP-A-Heisei 9-326828) corresponding to U.S. patent application Ser. No. 08/656,546 discloses a data packet router. In this reference, a data array having the number of data elements corresponding to the number of switch elements is provided in correspondence with a switch element matrix. First and second pseudo random shuffle patterns are generated to each of a series of intervals of connections of data sources and data destinations. The data sources are allocated to the data elements in accordance with the first current pseudo random shuffle pattern. The data destinations are allocated to the data elements in accordance with the second current pseudo random shuffle pattern. An increment test is carried out for the sources and the destinations over the data array to search a matching of a not-allocated source to the destination. The matching is allocated to the switch element corresponding to the data element. In this case, the first shuffle pattern is biased for the data source having the first priority level higher than a second priority level to be positioned near the start point of the increment test. After the whole data array is tested, the switch element is operated for the subsequent interval in accordance with the allocation for the current interval.
Therefore, an object of the present invention is to provide a scheduler in which the memory capacity of a memory for storing shuffle patterns can be reduced.
Another object of the present invention is to provide a scheduler in which a shuffling operation can be carried out when data with the number of input paths M is different from the number of output paths N.
Still another object of the present invention is to provide a scheduler in which a shuffling operation can be carried out for input paths or output paths with different priority levels.
In order to achieve an aspect of the present invention, in a scheduler having m input interfaces and n output interfaces in an ATM switching apparatus, each of m and n is an integer equal to or more than 2. The scheduler is includes a storage unit, first and second rearranging unit, a control unit and a searching unit. The storage unit stores a plurality of shuffle patterns including first to fourth shuffle patterns. The first rearranging unit carries out a first shuffling operation in units of k data (k is an integer equal to or more than 2 and less than or equal to s which is one of n and m, the other being t) and a second shuffling operation in units of u groups (u is an integer equal to or more than 2 and corresponding to s/k) to (mxc3x97n) data supplied from the m input interfaces based on the first and second shuffle patterns to produce first rearranged data. The (mxc3x97n) data are grouped into (txc3x97u) groups. The second rearranging unit carries out a third shuffling operation in units of p data (p is an integer equal to or more than 2 and less than or equal to (mxc3x97n)) and a fourth shuffling operation in units of groups to the first rearranged data based on the third and fourth shuffle patterns to produce second rearranged data. The first rearranged data are grouped into v groups (v is an integer equal to or more than 2 and corresponding to (mxc3x97n)/p). The control unit reads out the first to fourth shuffle patterns to supply to the first and second rearranging units. The searching unit outputs a permission signal for a relation between one input interface and one output interface based on the second rearranged data and a predetermined algorithm.
In this case, it is desirable that the storage unit includes a plurality of memories, which stores the plurality of shuffle patterns in units of sizes of the plurality of shuffle patterns.
Also, the first rearranging unit may include (txc3x97u) rearranging units and t third rearranging units. Each of the (txc3x97u) rearranging units carries out the first shuffling operation to corresponding ones of the (mxc3x97n) data based on the first shuffle pattern to produce third rearranged data. Each of the t third rearranging units is provided for u of the (txc3x97u) rearranging units to carry out the second shuffling operation to corresponding u groups of the third rearranged data based on the second shuffle pattern to produce (the first rearranged data)/t.
Alternatively, each of the t third rearranging units is provided to carry out the second shuffling operation to corresponding u groups of the (txc3x97u) groups based on the second shuffle pattern to produce fourth rearranged data. Each of the (txc3x97u) rearranging units carries out the first shuffling operation to corresponding one of (the fourth rearranged data)/u based on the first shuffle pattern to produce (the first rearranged data)/(txc3x97u).
Also, the second rearranging unit may include v fifth rearranging units, and a sixth rearranging unit. Each of the v fifth rearranging units carries out the third shuffling operation to corresponding p data of the first rearranged data based on the third shuffle pattern to produce fifth rearranged data. The sixth rearranging unit carries out the fourth shuffling operation to the v fifth rearranged data based on the fourth shuffle pattern to produce the second rearranged data.
Alternatively, the sixth rearranging unit carries out the fourth shuffling operation to the first rearranged data based on the fourth shuffle pattern to produce the sixth rearranged data. Each of the v fifth rearranging units carries out the third shuffling operation to corresponding data of (the sixth rearranged data)/v based on the third shuffle pattern to produce (the second rearranged data)/v.
Also, the control unit may allocate ones selected in a same probability from among the plurality of shuffle patterns stored in the storage unit based on the number of data to be rearranged as the first to fourth shuffle patterns.
Also, each of the plurality of shuffle patterns has a priority level, and the control allocates ones selected in a specified probability from among the plurality of shuffle patterns based on the number of data to be rearranged as the first to fourth shuffle patterns.
Also, it is desirable that k is a common divisor of m and n. Also, it is desirable that when s is not a common multiple of k, dummy data are added to one of the u groups such that the number of data in the one group is equal to k.
In order to achieve another aspect of the present invention, there is provided a method of shuffling (mxc3x97n) in a scheduler having m input interfaces and n output interfaces, each of m and n being an integer equal to or more than 2. The method is attained by (a) carrying out a first shuffling operation in units of k data (k is an integer equal to or more than 2 and less than or equal to s which is one of n and m, the other being t) and a second shuffling operation in units of u groups (u is an integer equal to or more than 2 and corresponding to s/k) to (mxc3x97n) data supplied from the m input interfaces based on the first and second shuffle patterns to produce first rearranged data, the (mxc3x97n) data being grouped into (txc3x97u) groups, by (b) carrying out a third shuffling operation in units of p data (p is an integer equal to or more than 2 and less than or equal to (mxc3x97n)) and a fourth shuffling operation in units of groups to the first rearranged data based on the third and fourth shuffle patterns to produce second rearranged data, the first rearranged data being grouped into v groups (v is an integer equal to or more than 2 and corresponding to (mxc3x97n)/p), and by outputting a permission signal for a relation between one input interface and one output interface based on the second rearranged data and a predetermined algorithm.
Also, a plurality of shuffle patterns are stored in units of sizes of the plurality of shuffle patterns.
Also, the (a) carrying out may be attained by (c) carrying out the first shuffling operation to the (mxc3x97n) data in units of k data based on the first shuffle pattern to produce a third rearranged data; and (d) carrying out the second shuffling operation to the third rearranged data in units of u groups based on the second shuffle pattern to produce the first rearranged data.
Alternatively, the (a) carrying out may be attained by (e) carrying out the second shuffling operation to the (mxc3x97n) data in units of u groups based on the second shuffle pattern to produce the fourth rearranged data; and by (f) carrying out the first shuffling operation to the fourth rearranged data in units of k data based on the first shuffle pattern to produce the first rearranged data.
Also, the (b) carrying out may be attained by (g) carrying out the third shuffling operation to the first rearranged data in units of p data based on the third shuffle pattern to produce fifth rearranged data; and by (h) carrying out the fourth shuffling operation to the fifth rearranged data based on the fourth shuffle pattern to produce the second rearranged data.
Alternatively, the (b) carrying out may be attained by (i) carrying out the fourth shuffling operation to the first rearranged data in units of groups based on the fourth shuffle pattern to produce sixth rearranged data; and by (j) carrying out the third shuffling operation to the sixth rearranged data in units of p data based on the third shuffle pattern to produce the second rearranged data.
Also, the first to fourth shuffle patterns may be selected in a same probability from among the plurality of shuffle patterns based on the number of data to be rearranged.
Alternatively, the first to fourth shuffle patterns may be selected in a specified probability from among the plurality of shuffle patterns based on the number of data to be rearranged.
Also, it is desirable that k is a common divisor of m and n. Alternatively, it is desirable that when s is not a common multiple of k, dummy data are added to one of the u groups such that the number of data in the one group is equal to k.